/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package org.gephi.statistics.spi.path;

/**
 *
 * @author lczgywzyy
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

public class LAF {
	
	Logger logger = LogManager.getLogger();

	boolean isAF = true;
	LGraph lgraph;
	int n;
	int start, end;
	Stack<Integer> theStack;

//	private ArrayList<Integer> tempList;
	private HashMap<Integer, Integer> tempList;
	private String counterexample;

	private ArrayList<String> resultText = new ArrayList<String>();

	public LAF(LGraph lgraph, int start, int end) {
		this.lgraph = lgraph;
		this.start = start;
		this.end = end;
	}

	@SuppressWarnings("rawtypes")
	public boolean getResult() {
		// lgraph.printGraph();
		n = lgraph.getN();
		theStack = new Stack<Integer>();

		if (!isConnectable(start, end)) {
			isAF = false;
			counterexample = "节点之间没有通路";
		} else {
			Iterator iter = lgraph.getVertexList().entrySet().iterator();
			while (iter.hasNext()) {
				Map.Entry entry = (Map.Entry) iter.next();
				int key = (int) entry.getKey();
				tempList = new HashMap<Integer, Integer>();
				Iterator iter2 = lgraph.getVertexList().entrySet().iterator();
				while (iter2.hasNext()) {
					Map.Entry entry2 = (Map.Entry) iter2.next();
					int key2 = (int) entry2.getKey();
					tempList.put(key2, 0);
				}
				lgraph.getVertexList().get(key).setAllVisitedList(tempList);
			}

			isAF = af(start, end);
		}
		return isAF;
	}

	@SuppressWarnings("rawtypes")
	private boolean af(int start, int end) {
		lgraph.getVertexList().get(start).setWasVisited(true); // mark it
		theStack.push(start); // push it

		while (!theStack.isEmpty()) {
			int v = getAdjUnvisitedVertex(theStack.peek());
			if (v == -1) // if no such vertex,
			{
				tempList = new HashMap<Integer, Integer>();
				Iterator iter = lgraph.getVertexList().entrySet().iterator();
				while (iter.hasNext()) {
					Map.Entry entry = (Map.Entry) iter.next();
					int key = (int) entry.getKey();
					tempList.put(key, 0);
				}
				lgraph.getVertexList().get(theStack.peek()).setAllVisitedList(tempList);// 把栈顶节点访问过的节点链表清空
				theStack.pop();
			} else // if it exists,
			{
				theStack.push(v); // push it
			}

			if (!theStack.isEmpty() && end == theStack.peek()) {
				lgraph.getVertexList().get(end).setWasVisited(false); // mark it
				printTheStack(theStack);
				theStack.pop();
			}
		}

		return isAF;
	}

	// 判断连个节点是否能连通
	@SuppressWarnings("rawtypes")
	private boolean isConnectable(int start, int end) {
		ArrayList<Integer> queue = new ArrayList<Integer>();
		ArrayList<Integer> visited = new ArrayList<Integer>();
		queue.add(start);
		while (!queue.isEmpty()) {
			Iterator iter = lgraph.getVertexList().entrySet().iterator();
			while (iter.hasNext()) {
				Map.Entry entry = (Map.Entry) iter.next();
				int key = (int) entry.getKey();
				if (LSparse_Matrix.getInstance().getValue(start, key) == 1 && !visited.contains(key)) {
					queue.add(key);
				}
			}
			if (queue.contains(end)) {
				return true;
			} else {
				visited.add(queue.get(0));
				queue.remove(0);
				if (!queue.isEmpty()) {
					start = queue.get(0);
				}
			}
		}
		return false;
	}

	public String counterexample() {
		for (Integer integer : theStack) {
			counterexample += lgraph.displayVertex(integer);
			if (integer != theStack.peek()) {
				counterexample += "-->";
			}
		}

		return counterexample;
	}

	// 与节点v相邻，并且这个节点没有被访问到，并且这个节点不在栈中
	@SuppressWarnings("rawtypes")
	public int getAdjUnvisitedVertex(int v) {
		HashMap<Integer, Integer> arrayList = lgraph.getVertexList().get(v).getAllVisitedList();
		Iterator iter = lgraph.getVertexList().entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			int key = (int) entry.getKey();
			if (LSparse_Matrix.getInstance().getValue(v, key) == 1 && arrayList.get(key) == 0 && !theStack.contains(key)) {
				lgraph.getVertexList().get(v).setVisited(key);
				return key;
			}
		}
		return -1;
	} // end getAdjUnvisitedVertex()

	public void printTheStack(Stack<Integer> theStack2) {
		String tmpString = "";
		for (Integer integer : theStack2) {
//			System.out.print(lgraph.displayVertex(integer));
			tmpString += lgraph.displayVertex(integer);
			if (integer != theStack2.peek()) {
//				System.out.print("-->");
				tmpString += "-->";
			}
		}
//		System.out.print("\n");
//		logger.info(tmpString);
		resultText.add(tmpString);
	}

	public String getResultText() {
		String tmpString = "";
		for (String s : resultText) {
			tmpString += s + "\n";
		}
		return tmpString;
	}
	public HashSet<String> getResultTextList() {
		HashSet<String> tmpStringList = new HashSet<String>();
		for (String s : resultText) {
			tmpStringList.add(s);
		}
		return tmpStringList;
	}
}
